package dynamicprogramming;

import org.junit.Test;

/**
 * 我们有一个数字序列包含 n 个不同的数字，如何求出这个序列中的最长递增子序列长度？比如 2, 9, 3, 6, 5, 1, 7
 * 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。
 */
public class ShortestPath3 {
    private int[] array = new int[]{2, 9, 3, 6, 5, 1, 7};
    private int longestSize = Integer.MIN_VALUE;

    public void getShortestPath() {
        int[] state = new int[array.length];
        state[0] = 1;
        for (int i = 1; i < state.length; i++) {
            for (int j = 0; j < i; j++) {
                if(array[i] > array[j]){
                    state[i] = Math.max(state[i], state[j]+1);
                }
            }
        }

        for (int j : state) {
            longestSize = Math.max(j, longestSize);
        }
        System.out.println(longestSize);
    }

    @Test
    public void test(){
        getShortestPath();
    }
}
